package leetcode;

/*
501. 二叉搜索树中的众数
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
假定 BST 有如下定义：
结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
例如：
给定 BST [1,null,2,2],
   1
    \
     2
    /TreeNode
   2
返回[2].
提示：如果众数超过1个，不需考虑输出顺序
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
通过次数18,210提交次数39,853
*/

public class problems_501 {
    public static void main(String[] args) {
        TreeNode A1 = new TreeNode(1);
        TreeNode A2 = new TreeNode(2);
        TreeNode A3 = new TreeNode(2);
        TreeNode A4 = new TreeNode(3);
        TreeNode A5 = new TreeNode(4);
        TreeNode A6 = new TreeNode(4);
        TreeNode A7 = new TreeNode(3);
        A1.left = A2;
        A1.right = A3;
        A2.left = A4;
        A2.right = A5;
        A3.left = A6;
        A3.right = A7;
        System.out.println(new Solution().findMode(A1));
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static class Solution {
        private TreeNode pre = null; // 前一个节点
        private int[] ret;
        private int retCount = 0;
        private int maxCount = 0;
        private int currCount = 0;

        public int[] findMode(TreeNode root) {
            inOrder(root);
            pre = null;
            ret = new int[retCount];
            retCount = 0;
            currCount = 0;
            inOrder(root);
            return ret;
        }

        private void inOrder(TreeNode node) {
            if (node == null) return;
            inOrder(node.left); // 左节点
            // 当前节点的重复数量
            if (pre != null && pre.val == node.val) {
                currCount++;
            } else {
                currCount = 1;
            }
            //
            if (currCount > maxCount) {
                // 不一致时
                maxCount = currCount;
                retCount = 1;
            } else if (currCount == maxCount) {
                //
                if (ret != null) ret[retCount] = node.val;
                retCount++;
            }
            pre = node;
            inOrder(node.right);  // 右节点
        }
    }
}